<?php
/**
 *  User：LRZ
 *  Date：2020/2/9
 *  Time：16:16
 */

/**
 *  69.x的平方根
 *
 *  标签：数学、二分查找
 *
 *  实现 int sqrt(int x) 函数。
 *  计算并返回 x 的平方根，其中 x 是非负整数。
 *  由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
 *
 *  示例 1:
 *      输入: 4
 *      输出: 2
 *
 *  示例 2:
 *      输入: 8
 *      输出: 2
 *      说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/sqrtx
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$x   = 8;
$res = mySqrt($x);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function mySqrt($x)
{
    if ($x <= 1) {
        return $x;
    }
    $left  = 0;
    $right = floor($x / 2);

    while ($left < $right) {
        $mid  = floor(($left + $right) / 2 + 1);
        $sqrt = $mid * $mid;

        if ($sqrt > $x) {
            $right = $mid - 1;
        } else {
            $left = $mid;
        }
    }

    return (int)$left;
}